//1. 时间复杂度：O(mn),空间复杂度：O(mn)
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        
        vector<int> ret;
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> judge(m, vector<int>(n, 0));
        int ans = m*n;
        int step = 1;
        ret.push_back(matrix[0][0]);
        judge[0][0] = 1;
        int i=0,j=0;
        while(step < ans) {

            for(j = j+1; j < n && judge[i][j]!=1; ++j) {
                judge[i][j]=1;
                ret.push_back(matrix[i][j]);
                step++;
            }
           --j;
            for(i = i + 1; i < m  && judge[i][j] != 1; ++i) {
                judge[i][j]=1;
                ret.push_back(matrix[i][j]);
                step++;
            }
            --i;
            for(j = j-1; j >= 0 && judge[i][j]!=1; --j) {
                judge[i][j]=1;
                ret.push_back(matrix[i][j]);
                step++;
            }
           ++j;
            for(i = i-1; i >= 0 && judge[i][j]!=1; --i) {
                judge[i][j]=1;
                ret.push_back(matrix[i][j]);
                step++;
            }
            ++i;
           
  
        }

        return ret;
    }
};

//2.空间复杂度：O(1)--->边界标记法

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        int m = matrix.size();
        int n = matrix[0].size();
        int top=0,bottom=m-1,left=0,right=n-1;
        while(left<=right && top<=bottom) {
            //向右走
            for(int i=left;i<=right && top<=bottom;++i){
                ans.push_back(matrix[top][i]);
            }
            top++;
            //向下走
            for(int i=top;i<=bottom && left<=right;++i){
                ans.push_back(matrix[i][right]);
            }
            right--;
            //向左走
            for(int i=right;i>=left && top<=bottom;--i){
                ans.push_back(matrix[bottom][i]);
            }
            bottom--;
            //向上走
            for(int i=bottom;i>=top && left<=right;--i){
                ans.push_back(matrix[i][left]);
            }
            left++;

        }
        
        return ans;
    }
};






